﻿//#define _CRT_SECURE_NO_WARNINGS 1
//@[Toc](leetcode)
//# 16. 最小覆盖子串（hard）
//[最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/description/)
//
//```cpp
//#define MAX 100001
//class Solution {
//public:
//    string minWindow(string s, string t) {
//        int src_hash[128];
//        int kind = 0;//统计子串字符种类数
//        int len = MAX;//标志最长数
//        int begin = -1;
//        for (auto ch : t)
//        {
//            if (src_hash[ch] == 0)
//                kind++;
//            src_hash[ch]++;
//        }
//        int des_hash[128];
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//        {
//            char in = s[right];
//            des_hash[in]++;//进窗口
//            if (des_hash[in] == src_hash[in])count++;//只有字符相同且数量相同才是相同的种类
//            while (count == kind)//更新结果
//            {
//                if (len > right - left + 1)
//                {
//                    len = right - left + 1;
//                    begin = left;
//                }
//                char out = s[left];
//                if (des_hash[out] == src_hash[out])count--;//只有字符相同且数量相同才是相同的种类
//                des_hash[out]--;
//                left++;
//            }
//        }
//        if (begin == -1)
//            return{};
//        else
//            return s.substr(begin, len);
//    }
//};
//```
//
//# 17. 二分查找（easy）
//
//```cpp
//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int mid = left + (right - left) / 2;//向下取整
//            if (nums[mid] > target)
//                right = mid - 1;
//            else if (nums[mid] < target)
//                left = mid + 1;
//            else return mid;
//        }
//        return -1;
//    }
//};
//```
//
//
//# 18. 在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
//
//[在排序数组中查找元素的第⼀个和最后⼀个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/574602128/)
//
//```cpp
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        //处理边界情况
//        if (nums.size() == 0)
//            return { -1,-1 };
//        //找左端点和右端点
//        //找左端点
//        //左端点的左区间是小于target，右区间是大于等于target
//        //左端点就是左区间趋近右区间最后重合的地方
//        //右端点的左区间是小于等于target，右区间是大于target
//        //右端点就是右区间趋近左区间区间最后重合的地方
//        int left = 0, right = nums.size() - 1;
//        int begin = 0;//标记左端点
//        while (left < right)//left等于right时为左端点另做判断
//        {
//            int mid = left + (right - left) / 2;//左区间在动因此向上取整
//            if (nums[mid] < target)
//            {
//                left = mid + 1;
//            }
//            else
//            {
//                right = mid;
//            }
//        }
//        if (nums[left] == target)
//            begin = left;
//        else return{ -1,-1 };
//
//        left = 0, right = nums.size() - 1;
//        while (left < right)//left等于right时为右端点另做判断
//        {
//            int mid = left + (right - left + 1) / 2;//左区间不动因此向下取整
//            if (nums[mid] <= target)
//            {
//                left = mid;
//            }
//            else
//            {
//                right = mid - 1;
//            }
//        }
//        return { begin,right };
//    }
//};
//```
//
//# 19.搜索插入位置（easy）
//[搜索插入位置](https://leetcode.cn/problems/search-insert-position/description/)
//
//```cpp
//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target) {
//        //找左端点
//        //左端点的左区间小于target
//        //左端点的右区间大于等于target
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        if (nums[left] < target)
//            return left + 1;
//        return left;
//    }
//};
//```
//
//# 20. x的平方根（easy）
//[x的平方根](https://leetcode.cn/problems/sqrtx/submissions/574609266/)
//```cpp
//class Solution {
//public:
//    int mySqrt(int x) {
//        //右端点问题
//        if (x < 1)return 0;//处理边界情况
//        int left = 1, right = x;
//        while (left < right)
//        {
//            long long mid = left + (right - left + 1) / 2;
//            long long sqrt = mid * mid;
//            if (sqrt <= x)
//            {
//                left = mid;
//            }
//            else
//            {
//                right = mid - 1;
//            }
//        }
//        return left;
//    }
//};
//```